ABC088 D - Grid Repainting
https://atcoder.jp/contests/abc088/tasks/abc088_d
提出
code: python
from collections import deque
h, w = map(int, input().split())
s = list(input()) for _ in range(h)
visited = list(False for _ in range(w)) for _ in range(h)
que = deque(0, 0)
while (len(que)):
now = que.popleft()
for i, j in -1, 0], 0, 1, 0, -1, [1 ,0:
go = [now0 + i, now1 + j]
if go == h-1, w-1:
break
if go0 < 0 or go0 >= h or go1 < 0 or go1 >= w:
continue
if s[go0][go1] == '#':
continue
if visited[go0][go1] == False:
que.append([go0, go1])
visited[go0][go1] = True
ans = 0
for i in range(h):
for j in range(w):
if (sij == "." and visitedij == False):
ans += 1
print(ans)
解答
code: python
from collections import deque
h, w = map(int,input().split())
s = input() for _ in range(h)
dis = [0 * w for _ in range(h)]
dis00 = 1
que = deque(0, 0)
while que:
nowi, nowj = que.popleft()
for i, j in 1, 0], -1, 0, 0, 1, [0, -1:
nexti, nextj = nowi + i, nowj + j
if nexti < 0 or nexti > h-1 or nextj < 0 or nextj > w-1 or snextinextj == "#" or disnextinextj != 0:
continue
else:
disnextinextj = disnowinowj + 1
que.append(nexti, nextj)
if dish-1w-1 == 0:
print(-1)
else:
sharp = 0
for i in range(h):
sharp += si.count("#")
print(h*w - dish-1w-1 - sharp)
テーマ
#bfs
蟻本 2-1 迷路の最短路
提出
AC/WA
code: python
from collections import deque
h, w = map(int, input().split())
s = list(input()) for _ in range(h)
que = deque(0, 0)
dis = [0 * w for _ in range(h)]
dis00 = 1
while que:
nowi, nowj = que.popleft()
for i, j in 1, 0], -1, 0, 0, 1, [0, -1:
nexti, nextj = nowi + i, nowj + j
if nexti < 0 or nexti > h-1 or nextj < 0 or nextj > w-1 or snextinextj == "#" or disnextinextj != 0:
continue
else:
disnextinextj = disnowinowj + 1
que.append(nexti, nextj)
res = dish-1w-1
if res == 0:
print(-1)
else:
visited = False * pow(10, 3)
ans = 0
for i in range(h):
for j in range(w):
if sij == "#":
continue
if visited[disij - 1]:
ans += 1
else:
visited[disij - 1] = True
print(ans)